package array;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * 以数组 intervals 表示若干个区间的集合，
 * 其中单个区间为 intervals[i] = [starti, endi] 。
 * 请你合并所有重叠的区间，并返回 一个不重叠的区间数组，
 * 该数组需恰好覆盖输入中的所有区间 。
 *
 */
public class MergeInterval {
    @Test
    public void merge() {
        int[][] inter = new int[][]{{-1,8},{2,5},{8,9},{10,18},{21,30}};
        bubbleSort(inter);
        Arrays.sort(inter,(a,b)->a[0] - b[0]);
//        for (int[] ints : inter) {
//            System.out.println(ints[1]);
//        }
        ArrayList<int[]> result = new ArrayList<>();
        int left = 0;
        int right = 1;
        while (right <= inter.length){
            if(right < inter.length && inter[left][1] >= inter[right][0]){
                if(inter[left][1] > inter[right][1]){
                    right++;
                    continue;
                }
                inter[left][1] = inter[right][1];
            }else{
                result.add(inter[left]);
                left = right;
            }
            right++;
        }
        for (int[] ints : result) {
            for (int anInt : ints) {
                System.out.println(anInt);
            }
        }
        result.toArray(new int[result.size()][2]);
    }
    public void bubbleSort(int[][] nums){
        // 3,2,4,5,1
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums.length - i - 1; j++) {
                if(nums[j][0] > nums[j + 1][0]){
                    int[] swap = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = swap;
                }
            }
        }
    }
}
